package YuanFuDao2;


/**
 * 链表m到n反转
 */
public class Main10 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(7);
        head.next.next.next = new ListNode(5);
        head.next.next.next.next = new ListNode(9);
        //head.show();
        //help(head,2,4).show();
        //help3(head).show();
        //System.out.println(help5(head));
        //System.out.println(findDaoKNode(head,2).val);

        ListNode node = reverseKGroup(head,2);
        node.show();
    }

    // 链表m到n反转
    public static ListNode help(ListNode head,int m,int n){
        if(head == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 1; i < m; i++) {
            pre = pre.next;
        }
        head = pre.next;

        int delta = n-m;
        while(delta > 0){
            ListNode next = head.next;
            head.next = next.next;
            next.next = pre.next;
            pre.next = next;
            delta--;
        }
        return dummy.next;
    }


    // 链表翻转  递归
    public static ListNode help2(ListNode head){
        if(head == null || head.next == null) return head;

        ListNode res = help2(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }

    public static ListNode help3(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }



    // 回文链表
    public static boolean help4(ListNode head){
        if(head == null || head.next == null) return true;
        ListNode fast = head;
        ListNode slow = head;
        ListNode p = null;
        ListNode pre = null;
        // 用快慢指针遍历的同时翻转前半部分，然后与后半部分比较即可。
        while(fast != null && fast.next !=null){
            p = slow;
            fast = fast.next.next;
            slow = slow.next;
            // 翻转
            p.next = pre;
            pre = p;
        }

        if(fast!=null){  //奇数个节点时跳过中间节点
            slow = slow.next;
        }

        while(slow!=null){
            if(p.val != slow.val){
                return false;
            }
            p = p.next;
            slow = slow.next;
        }
        return true;
    }

    public static boolean help5(ListNode head){

        if(head == null || head.next == null) return true;

        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){  // 找到中间节点
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode first = slow.next;
        ListNode reverseHead = null;
        while(first != null){  // 翻转后半部分
            ListNode second = first.next;
            first.next = reverseHead;
            reverseHead = first;
            first = second;
        }

        while(reverseHead != null){  // 比较
            if(reverseHead.val != head.val){
                return false;
            }
            reverseHead = reverseHead.next;
            head= head.next;
        }
        return true;
    }


    // 返回单链表的倒数第K个节点
    public static ListNode findDaoKNode(ListNode head,int k){
        if(head == null || k < 1) return null;
        ListNode fast = head;
        ListNode slow = head;

        for (int i = 0; i < k; i++) {
            if(fast == null) return null;  // 防止k太大了，超过了链表的长度
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }


    // 链表每隔K个反转
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode start = head;
        ListNode end = head;
        ListNode next = head;

        while(next!=null){

            for (int i = 1; i < k && end != null; i++) {
                end = end.next;
            }

            if(end == null){  // 最后一段不够k个节点
                break;
            }

            next = end.next;
            end.next = null;
            end = start;
            start = reverse(start);
            end.next = next;
            pre.next = start;

            // 重新指定pre start end
            pre = end;
            start = next;
            end = start;
        }
        return dummy.next;
    }


    // 反转以head为头结点的链表,并返回链表的头结点
    public static ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;

        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

}





class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }

      public void show(){
          ListNode p = this;
          while(p!=null){
              System.out.print(p.val + " ");
              p = p.next;
          }
          System.out.println();
      }

}

